/**
 * Convert Sorted Array to Binary Search Tree
Given an array where elements are sorted in ascending order, 
convert it to a height balanced BST.
 */
package com.xinpan.exercise;

public class SortedArrayToBST {
    public TreeNode sortedArrayToBST(int[] num) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(num.length == 0)
            return null;
        
        int last = num.length - 1;
        int mid = last / 2;
        TreeNode root = new TreeNode(num[mid]);
        root.left = createBST(0, mid-1, num);
        root.right = createBST(mid+1, last, num);
        
        return root;
    }
    
    public TreeNode createBST(int s, int e, int[] num)
    {
        if(e < s)
            return null;
        int mid = (e+s)/2;
        TreeNode root = new TreeNode(num[mid]);
        root.left = createBST(s, mid-1, num);
        root.right = createBST(mid+1, e, num);
        
        return root;
    }
    
    class TreeNode {
    	 int val;
    	 TreeNode left;
    	 TreeNode right;
    	 TreeNode(int x) { val = x; }
    	 }
}
